package com.shuang.tree39;

import java.util.ArrayList;
import java.util.List;

public class FindMode {

    //递归 中序遍历-不使用额外空间，利用二叉搜索树特性

    //定义全局变量
    //记录前一个结点
    TreeNode pre;
    //用于计数 每个节点出现的次数
    int count;
    //用于记录节点出现的最大频率（因为众数可能有多个，还可以利用此变量避免出现二次遍历）
    int maxCount;
    //用于封装结果的集合
    List<Integer> resList;

    public int[] findMode(TreeNode root) {
        //初始化全局变量
        resList = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;

        //递归实现封装结果集合
        findMode1(root);

        //将集合转为数组返回
        int[] res = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            res[i] = resList.get(i);
        }

        return res;
    }

    //递归函数封装结果 中序遍历
    public void findMode1(TreeNode root) {

        //终止条件
        if (root == null) {
            return;
        }

        //左
        findMode1(root.left);

        //zhong
        if (pre == null || root.val != pre.val) {
            //pre等于空证明是第一个节点时（根节点） 计数为一
            //或者当前节点值不等于前一个值时 计数为一
            count = 1;
        } else {
            //当前节点和前一个结点相等 计数加一
            count++;
        }

        //处理封装结果 以及maxCount
        if (count > maxCount) {

            //先清空之前存过的集合中的值
            resList.clear();

            //更新最大计数
            maxCount = count;

            //并把当前节点值存到结果集合中
            resList.add(root.val);

        } else if (count == maxCount) {
            //该节点出现次数和最大次数一致 将该节点值也存到集合中
            resList.add(root.val);
        }

        //更新前一个结点位置
        pre = root;

        //you
        findMode1(root.right);
    }
}
